package com.tom.architect02.structure.chart2;

import android.util.Log;
import java.util.ArrayDeque;

/**
 * Created by hcDarren on 2018/11/11.
 * 普通表示：一维数组+二维数组
 * 邻接表来表示图：数组+链表
 * 带箭头：画两张表（出度表（逆向临接表）+入度表）
 * 十字链表：存储边节点，顶点结点。
 *
 */
public class Graph {
    public final static int MAX_WEIGHT = Integer.MAX_VALUE; // 无穷大
    // 顶点的个数
    int vertexSize;
    // 顶点的集合
    int[] vertexes;
    // 边的集合
    int[][] matrix;

    public Graph(int vertexSize, int[] vertexes, int[][] matrix) {
        this.vertexSize = vertexSize;
        this.vertexes = vertexes;
        this.matrix = matrix;
    }

    // 广度优先的搜索 遍历
    public void breadthFirstSearch() {
        // 访问过的顶点角标，标记为true
        boolean[] visited = new boolean[vertexSize];
        // 把第一个顶点加入队列。 双端队列ArrayDeque
        ArrayDeque<Integer> vertexQ = new ArrayDeque<>();
        vertexQ.push(vertexes[3]); // 加入根节点3

        while (!vertexQ.isEmpty()) { // 队列不为空
            // 当前顶点，但是我们这里又是角标。 拿到并移除节点。
            int currentVertex = vertexQ.removeFirst();
            // 查询当前角标
            int index = currentVertex;

            // 当前节点有没有被访问过，要打印出来。访问过就丢弃。
            if (!visited[index]) { // O(1) 级别的时间复杂度。
                Log.e("TAG", "访问到了顶点：" + currentVertex);
                visited[index] = true; // 标记角标被访问了。

                for (int i = 0; i < vertexSize; i++) {
                    // matrix[index][i] == 1 代表与 index 相连
                    // !visited[i] 代表i角标没被访问过。
                    if (matrix[index][i] == 1 && !visited[i]) {
                        // 还可以写一个判断，如果队列中不包含 再往里面新增 , 画蛇添足
                        // if(!vertexQ.contains(vertexes[i])) {  // 0(N)
                        vertexQ.addLast(vertexes[i]); // 加到队列尾
                        // }
                    }
                }
            } // end if
        } // end of while.
    }


    // 最小生成树 prim 算法。
    public void prim() {
        // 0. 定义一个数组内存，当前修好村庄 , lowcost = 0 代表已经修了
        int[] lowcost = new int[vertexSize]; // vertexSize顶点的数量 9

        // 1. 第一列的数据先放到 lowcost 里面来。作为初始值。
        for (int i = 0; i < vertexSize; i++) {
            lowcost[i] = matrix[0][i];
        }
        int sum = 0; // 总修路的距离

        // 2. 起点是index=0的点。外层循环从点①遍历到点⑧即可。
        for (int i = 1; i < vertexSize; i++) { // i=1,自己(0)不要考虑。
            int min = MAX_WEIGHT; // 记录最小的值
            int minId = 0; // 最小的id值

            // 3. 找最小非零(已经修好了)的修路 ，之间是否联通
            for (int j = 1; j  < vertexSize; j++) {
                // lowcost[j] < min 找到更小的了
                // lowcost[j] != 0  否则拿到的永远是0. 0代表已经修过了。
                if (lowcost[j] < min && lowcost[j] != 0) {
                    min = lowcost[j]; // 更新权值
                    minId = j;
                }
            }
            // 4. 找到目标村庄，打印。将已修好的点lowcost[minId] 置零。sum累加。
            Log.e("TAG", "找到村庄：" + vertexes[minId] + " , 修路距离：" + min);
            lowcost[minId] = 0; // 路已经修好了
            sum += min; // sum累加 最小的边。

            // 5. 有更小的值，淘汰之前考虑中的值。
            // 当前修路索引minId，相连的边，都考虑进来，存入lowcost数组。最外层for循环继续处理。
            for (int k = 0; k < vertexSize; k++) {
                // *边考虑边淘汰， matrix[minId][k]里面的值更小，就更新。*
                // lowcost[k] > 0 还没有修路。
                if (matrix[minId][k] < lowcost[k] && lowcost[k] > 0) {
                    lowcost[k] = matrix[minId][k]; // 作比较后，小于了 就替换上去。更新lowcost[k]
                }
            }

            // 6. 打印，观察当前locast中的值。
            for (int number : lowcost) {
                Log.e("TAG","number = " +number);
            }
            Log.e("TAG","==================================== ");
        } // end for i
        Log.e("TAG", "最短的路径是：" + sum); // 17
    }

}
